/**
 * https://leetcode-cn.com/problems/fibonacci-number/
 * 斐波那契数列
 */
// 动态规划的优化
const fib = (n: number): number => {
    // 边界判断
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;

    let left = 1,
        right = 1,
        ans = 1;

    // 从3开始
    for (let i = 3; i <= n; i++) {
        ans = left + right;
        left = right;
        right = ans
    }

    return ans
};

// 动态规划
const fib2 = (n: number): number => {
    // 边界判断
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;

    // dp[i]是第i个数的斐波那契数 
    // 状态转移方程: dp[i] = dp[i - 1] + dp[i - 2] 
    const dp: number[] = new Array(n + 1)

    // 确定初始值
    dp[0] = 0;
    dp[1] = dp[2] = 1;

    for (let i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
    return dp[n]
};





// 递归
const fib1 = (n: number): number => {
    // 边界判断
    if (n === 0) return 0;
    if (n === 1) return 1;

    // 递归调用
    return fib1(n - 1) + fib1(n - 2)
};